class MedianFinder:
    """就算是二分插入排序感觉还是很慢"""
    def __init__(self):
        self.memory = []

    def addNum(self, num: int) -> None:
        i, min_i, max_i = 0, -1, len(self.memory)
        while max_i - min_i > 1:
            if self.memory[i] == num:
                self.memory.insert(i, num)
                return
            elif self.memory[i] > num:
                i, max_i = (i + min_i) // 2, i
            else:
                i, min_i = (i + max_i) // 2, i
        self.memory.insert(max_i, num)

    def findMedian(self) -> float:
        length =  len(self.memory)
        if length % 2 == 0:
            return (self.memory[length//2-1] + self.memory[length//2]) / 2
        else:
            return self.memory[length//2] / 1


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class MedianFinder2:
    """这个写的比列表二分查找慢"""
    def __init__(self):
        self.head = ListNode(None)
        self.length = 0

    def addNum(self, num: int) -> None:
        new_note = ListNode(num)
        now_note = self.head
        while now_note.next and now_note.next.val < num:
            now_note = now_note.next
        now_note.next, new_note.next = new_note, now_note.next
        self.length += 1

    def findMedian(self) -> float:
        index, now_note = 0, self.head
        if self.length % 2 == 0:
            while index <= self.length / 2:
                if index == self.length // 2:
                    num = now_note.val
                index += 1
                now_note = now_note.next
            return (num + now_note.val) / 2
        else:
            while index < self.length / 2:
                index += 1
                now_note = now_note.next
            return now_note.val / 1


a = MedianFinder()
a.addNum(1)
a.addNum(2)
print(a.findMedian())
a.addNum(3)
print(a.findMedian())
